// 2025/9/17
// 串联所有单词的子串

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int n = words.size(), size = words[0].size();
        vector<int> ans;
        unordered_map<string, int> wordNum;
        for (auto& word : words)
            wordNum[word]++;
        for (int i = 0; i < size; i++)
        {
            vector<string> swords;
            for (int pos = i; pos < s.size(); pos += size)
            {
                swords.emplace_back(s.substr(pos, size));
            }
            unordered_map<string, int> sWordNum = wordNum;
            for (int left = 0, right = 0; right < swords.size(); right++)
            {
                if (!wordNum.count(swords[right]))
                {
                    sWordNum = wordNum;
                    left = right + 1;
                }
                else if (--sWordNum[swords[right]] == 0)
                {
                    sWordNum.erase(swords[right]);
                }
                else if(sWordNum[swords[right]] < 0)
                {
                    while (sWordNum[swords[right]] < 0)
                    {
                        if (++sWordNum[swords[left]] == 0)
                            sWordNum.erase(swords[left]);
                        left++;
                    }
                    sWordNum.erase(swords[right]);
                }

                if (sWordNum.empty())
                {
                    ans.emplace_back(i + left * size);
                }
            }
        }
        return ans;
    }
};